package com.github.hgkmail.hello.leetcode101.pointer.tree.bst;

import com.github.hgkmail.hello.leetcode101.base.CommonUtil;
import com.github.hgkmail.hello.leetcode101.base.TreeNode;

//dfs居然还能修剪二叉搜索树BST。。。
public class LC669TrimABinarySearchTree {

    public TreeNode dfs(TreeNode root, int low, int high) {
        if (root==null) {
            return null;
        }
        if (root.val<low) {
            //root和left都不要了
            return dfs(root.right, low, high);
        } else if (root.val>high) {
            //root和right都不要了
            return dfs(root.left, low, high);
        } else {
            root.left=dfs(root.left, low, high);
            root.right=dfs(root.right, low, high);
            return root;
        }
    }

    //使得所有节点的值在[low, high]中
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root==null) {
            return null;
        }
        //不喜欢在主函数直接搞递归
        return dfs(root, low, high);
    }

    public static void main(String[] args) {
        LC669TrimABinarySearchTree lc = new LC669TrimABinarySearchTree();
        TreeNode root= CommonUtil.deserializeBinaryTree("6,3,2,#,#,5,#,#,10,#,#");
        System.out.println(lc.findMax(root));
        System.out.println(lc.findMin(root));
//        lc.insertNode(root,7);
//        lc.insertNode(root,15);
        lc.insertNode(root, 4);
        System.out.println(CommonUtil.serializeBinaryTree(root));
        lc.deleteNode(root, 3);
        System.out.println(CommonUtil.serializeBinaryTree(root));

        System.out.println();
        TreeNode r=CommonUtil.deserializeBinaryTree("3,1,#,2,#,#,4,#,#");
        System.out.println(CommonUtil.serializeBinaryTree(lc.trimBST(r, 1,2)));
    }

    /////////BST常用操作/////////

    //找值最小的节点
    public TreeNode findMin(TreeNode root) {
        if (root==null || root.left==null) { //空节点或者叶子节点，直接返回
            return root;
        }
        return findMin(root.left);
    }

    //找值最大的节点
    public TreeNode findMax(TreeNode root) {
        if (root==null || root.right==null) { //null or leaf
            return root;
        }
        return findMax(root.right);
    }

    //删除节点，分类讨论
    public TreeNode deleteNode(TreeNode root, int x) {
        if (root==null) {
            return null;
        }
        if (x<root.val) { //在左子树
            root.left = deleteNode(root.left, x);
        } else if (x>root.val) { //在右子树
            root.right = deleteNode(root.right, x);
        } else { //相等
            if (root.left!=null && root.right!=null) { //有双子树的节点，需要用右子树的最小节点来取代
                TreeNode temp = findMin(root.right);
                root.val=temp.val;
                root.right=deleteNode(root.right, temp.val);
            } else { //其他情况，跟链表差不多
                root= root.left==null ? root.right : root.left;
            }
        }
        return root;
    }

    //插入节点
    public TreeNode insertNode(TreeNode root, int x) {
        if (root==null) {
            root = new TreeNode(x, null, null);
        } else if (x<root.val) {
            root.left=insertNode(root.left, x);
        } else if (x>root.val) {
            root.right=insertNode(root.right, x);
        }
//        else {
//            //找到了，已存在，不用做事情
//        }
        return root;
    }
}
